/* program search
   reads query, dictionary, term-doc matrix - reports relevance
*/


/* Set these parameters to control conversion and preferences */
long int nout=100;       /* print informations every nout tokens processed */
long int nsave=5000;     /* save every nsave tokens processed */
int nocase=1;            /* ignore case */
int precision=2;         /* no. of digits for printing matrix */



#include <stdio.h>
#include <string.h>
#include <math.h>

#define BUFLEN 4096
#define MAXTERMS 30
#define WLEN 30

double totall=0.;

struct st_node {
  char wrd[WLEN];
  long int lbl;
  struct st_node *l, *r;
};

long int ucnt, rdcnt, wcnt;
char fln[BUFLEN];
char fdn[]="dict.a"; FILE *fdp;
char fmn[]="tdm.dat"; FILE *fmp;
char w[WLEN];
char **dcv;
double *dcr;
char query[MAXTERMS][WLEN];
long int dc=1;
long int dcn=0;
double *v;

struct st_node * newnode(void);
void addcode(const char *, struct st_node **);
long int encode(const char *, struct st_node **);
long int words(struct st_node*);
char** getdocnames(char*fln);
double *vect(int);
char *string(int);

main(int argc, char *argv[])
{
  struct st_node *dicttree=NULL;
  int i,ix;
  double *qv, *dv;
  int tmp;

/* start command line */
  if (argc>2)
    fprintf(stderr,"WARNING - extra strings on command line\n");
  else if (argc==1)
    fprintf(stderr,"ERROR - no filename given on command line\n"),exit(-3);
  strcpy(fln,argv[1]);
/* end command line */

/* start initializing algorithm */
  ucnt=0;
  dcv=getdocnames(fln);
  dcr=vect(dcn);
/* end initializing algorithm */


/* start read dictionary */
  fdp=fopen(fdn,"r");
  if(!fdp) perror(fdn),exit(-1);
  for(i=1;i<=4;i++) fgets(fln,BUFLEN,fdp);
  while (!feof(fdp)){
    fgets(fln,BUFLEN,fdp);
    sscanf(fln,"%s",w);
    addcode(w,&dicttree);
  }
/* end read dictionary */

/* start prepare vectors */
  ucnt=words(dicttree);
  qv=vect(ucnt);
  dv=vect(ucnt);
/* end prepare vectors */

/* start process query (from stdin) */
  for(i=0;i<=MAXTERMS && !feof(stdin);i++) {
    getword(query[i], stdin);
/*DEBUG*/fprintf(stderr,"word = %s\n",query[i]);
    ix=encode(query[i],&dicttree);
    qv[ix]=1.;
  }
/* end process query (from stdin) */

/* start compute relevances */
  fmp=fopen(fmn,"r");
  if(!fmp) perror(fmn),exit(-1);
  fscanf(fmp,"%i",&tmp);
  if(tmp!=dcn) fprintf(stderr,"ERROR: no match in document number\n"),exit(-20);
  fscanf(fmp,"%i",&tmp);
  if(tmp!=ucnt) fprintf(stderr,"ERROR: no match in term number\n"),exit(-20);
  for(dc=1;dc<=dcn;dc++) {
    for(i=1;i<=ucnt;i++)
      fscanf(fmp,"%lf",&(dv[i]));
    dcr[dc]=0.;
    for(i=1;i<=ucnt;i++) {
      dcr[dc]+=qv[i]*dv[i];
    }
  }
/* end compute relevances */
  
/* start print relevances */
  for(dc=1;dc<=dcn;dc++) {
    printf("%.4lf %s\n",dcr[dc],dcv[dc]);
  }
/* end print relevances */

  fprintf(stderr,"END OF RUN\n");
}

struct st_node * newnode(void)
{
  struct st_node *tmp;
  const int memsize=100;
  static int imem=0;
  static struct st_node *mem=NULL;

  if (imem==0) {
    mem=(struct st_node *)malloc(memsize*sizeof(struct st_node));
    imem=memsize;
    if (mem==NULL)
      fprintf(stderr,"ERROR - memory allocation\n"),exit(-1);
    totall+=memsize*(double)sizeof(struct st_node)/1000.;
  }
  tmp=mem+(--imem);
  tmp->l=tmp->r=NULL;
  ucnt++;
  tmp->lbl=ucnt;
  return tmp;
}

void addcode(const char *s, struct st_node **t)
{
  int cmp;

  if ((*t)==NULL) {
    *t=newnode();
    strcpy((*t)->wrd,s);
    return;
  }
  cmp=strcmp(s,(*t)->wrd);
  if (cmp>0)
    return addcode(s,&((*t)->r));
  if (cmp<0)
    return addcode(s,&((*t)->l));
}

long int encode(const char *s, struct st_node **t)
{
  int cmp;

  if ((*t)==NULL) {
    return 0L;
  }
  cmp=strcmp(s,(*t)->wrd);
  if (cmp==0) {
    return (*t)->lbl;
  }
  if (cmp>0)
    return encode(s,&((*t)->r));
  if (cmp<0)
    return encode(s,&((*t)->l));
}

int getword(char *wbuf,FILE *fp)
{
  char c;
  int i;

/* start leggi token */
START:
  i=0;
  do {
    c=fgetc(fp);
  } while(!isalpha(c) && !feof(fp));
  if (feof(fp))
    return 0;
  do {
    wbuf[i++]=c;
    if (i>BUFLEN)
      fprintf(stderr,"ERROR: buffer overflow\n"),exit(-2);
    c=fgetc(fp);
  } while(isalpha(c) && !feof(fp));
  wbuf[i]='\0';
/* end leggi token */
  if(nocase)strlwr(wbuf);
/* start stoplisting */
  if (i<=2)
    goto START;
/* end stoplisting */

/* start stemming */
  stripsuffix("ing",w);
  stripsuffix("ities",w);
  stripsuffix("ity",w);
  stripsuffix("ly",w);
  stripsuffix("ed",w);
  stripsuffix("s",w);
  stripsuffix("e",w);
/* end stemming */
  return 1;
}

int stripsuffix(const char *s, char *w)
{
  int i,j;

  i=strlen(w);
  j=strlen(s);
  while (i>0 && j>0 && w[i]==s[j]) {
    i--, j--;
  }
  if (i>0 && j==0 && w[i]==s[j])
    w[i]='\0';
  return 1;
}

long int words(struct st_node *t)
{
  long int val=1;

  if (t==NULL)
    return 0.;
  val=val+words(t->l);
  val=val+words(t->r);
  return val;
}

char** getdocnames(char*fln)
{
  char **dcv;
  char nbuf[BUFLEN];
  FILE *flp;

  if ((flp=fopen(fln,"r"))==NULL)
    fprintf(stderr,"ERROR #6 - system reports:\n"), perror(fln), exit(-4);
  if(fgets(nbuf,BUFLEN,flp)==NULL) {
    fprintf(stderr,"ERROR - While scanning the list of document names:\n");
    fprintf(stderr,"Document name list ended prematurely\n");
    exit(-9);
  }
  if(sscanf(nbuf,"%li",&dcn)==0) {
    fprintf(stderr,"ERROR - While scanning the list of document names:\n");
    fprintf(stderr,"The list should start with the number of documents\n");
    exit(-7);
  }
  if(dcn==0) {
    fprintf(stderr,"ERROR - While scanning the list of document names:\n");
    fprintf(stderr,"The number of documents should be > 0\n");
    exit(-8);
  }
  dcv=(char**)malloc((1+dcn)*sizeof(char*));
  totall+=(double)((1+dcn)*sizeof(char*))/1000.;
  for(dc=1;dc<=dcn;dc++) {
    if(fgets(nbuf,BUFLEN,flp)==NULL) {
      fprintf(stderr,"ERROR - While scanning the list of document names:\n");
      fprintf(stderr,"Document name list ended prematurely\n");
      exit(-9);
    }
    dcv[dc]=string(BUFLEN);
    totall+=(strlen(nbuf)*sizeof(char))/1000.;
    if(dcv[dc]==NULL)
      fprintf(stderr,"ERROR - Out of memory for document name list\n"),exit(-1);
    strcpy(dcv[dc],nbuf);
    dcv[dc][strlen(nbuf)-1]='\0';
  }
  return dcv;
}

char *string(int len)
{
  char *s;

  s = (char *)
      malloc((size_t)(len * sizeof(char)));
  if(!s)
    fprintf(stderr,"allocazione non riuscita in string()"),exit(-1);
  else
    totall+=(double)(len * sizeof(char))/1000.;
  return s;
}

double *vect(int len)
{
  double *v;

  v = (double *)
      malloc((size_t) ((len + 1) * sizeof(double)));
  if(!v)
    fprintf(stderr,"allocazione non riuscita in vect()"),exit(-1);
  else
    totall+=(double)((len + 1) * sizeof(double))/1000.;
  return v;
}

